1. Field of the Invention This invention relates generally to iterative turbo decoding, and more particularly to adaptive halting algorithms that reduce computational complexity of iterative turbo decoders.
2. Description of the Prior Art
Turbo code is well known computational tool that was proposed in 1993 and that attracted the attention of researchers and developers, especially in the art of communication engineering. C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon Limit Error-correcting Coding and Decoding: Turbo Codes (I), Proc.ICC ""93, pp. 1064-1070, May 1993. The Berrou et al. reference is incorporated by reference herein. A turbo encoder is composed of two recursive systematic convolutional (RSC) encoders and an interleaver to generate the interleaved version of an input information sequence. The interleaved sequence is also encoded using one of the RSC encoders. The resultant turbo code, using parallel concatenation of the two RSC codes, has a substantially large free Hamming distance and therefore provides a powerful error correcting code. The aforesaid Hamming distance can be further improved by employing long interleavers a the expense of larger memory capacity.
FIG. 4 is a simplified block diagram of a parallel-concatenated rate 1/3 turbo encoder. A parallel-concatenated turbo encoder has two or more component encoders in conjunction with one or more interleavers. A component encoder C1 to create a parity sequence X1 encodes an input information sequence. The input information sequence is interleaved and then encoded by C2 to create a second parity sequence X2. The information sequence and the two parity sequences are then multiplexed to create a coded sequence.
The foregoing two RSC codes are alternately MAP-decoded in the turbo decoder, and the reliability of the soft output of the MAP decoder is iteratively updated. The sign of the soft output is improved as a decoded output following a sufficient number of iteration steps. The amplitude of the soft output gradually increases during the iteration process. However, the sign generally remains constant after several iteration steps. Thus, it is easy to recognize a decoded output can become error-free in just a few iteration steps for low-noise channels having a channel-decoded bit error rate (BER) as low as 10xe2x88x926. Detection of an error-free decoded sequence can significantly reduce computational complexity since the iteration process can then be halted without requiring further iteration computations.
A transmitted sequence is generally encoded with an error detection code such as the familiar cyclic redundancy check (CRC) code disclosed by S. Lin and D. J. Costello Jr., Error Control Coding: Fundamentals and Applications, Prentice Hall, N.J., 1983, and incorporated herein by reference. The above error-free decoding can then be checked for accuracy at the receiver side using the CRC code; and when error-free decoding is detected during an iteration, the remaining portion of the iteration can either be ignored or completely halted. A. Shibutani, H. Suda, and F. Adachi, Decoding-complexity Reduction On Turbo-CRC Concatenated Code in W-CDMA Mobile Radio, Proc IEICE General Conf., B-5-109, vol. 1, pp. 541, March 1999 (in Japanese), and incorporated by reference herein, have shown the effectiveness of the foregoing iterative turbo decoding process.
If a transmitted sequence is not encoded with the CRC code, the foregoing technique of Shibutani et al. cannot be applied however. Even if the transmitted sequence is encoded with the CRC code, the associated receiver decoder must a priori know the generator polynomial of the CRC code and the position of its redundancy check words in the received sequence. This limitation makes the design of the decoder complicated for variable rate data communications.
In J. Hagenauer, E. Offer, and L. Papke, Iterative Decoding of Binary Block and Convolutional Codes, IEEE Trans. Inf. Theory, vol. 42, pp. 429-445, March 1996 and in U.S. Pat. No. 5,761,248, entitled Method and Arrangement for Determining an Adaptive Abort Criterion in Iterative Decoding of Multi-dimensionally Coded Information, by J. Hagenauer and F. Burkert, issued June 1998, both references incorporated herein by reference, Hagenauer et al. have shown implementation of the adaptive halting algorithm without resorting to use of the transmitted CRC code. The adaptive halting algorithm of Hagenauer et al. makes use of the difference sequence between two soft output sequences determined at the iteration step as well as the preceding iteration step and derived at each iteration step. Then the L2 norm of the difference sequence (cross entropy of the two soft output sequences) is calculated at each iteration step. Once the cross entropy of the two soft output sequences becomes less than a predetermined threshold value, the iteration process is halted. Although the techniques developed by Hagenauer et al. do not require use of the transmitted CRC code, the technique otherwise requires an extra large memory capacity to store the soft output sequence data at each preceding iteration step. This is so since the soft output sequence of a typical turbo decoder is very long and therefore has soft output symbols with long word lengths. Further, the aforementioned cross entropy needs to be computed using high accuracy in order to accurately detect the convergence of iterative decoding, which significantly increases the hardware size of the multiplier used for the calculation of the L2 norm.
P. Robertson, Illuminating the Structure of Parallel Concatenated Recursive Systematic (TURBO) Codes, Proc. GLOBECOM""94, pp. 1298-1303, November 1994, incorporated by reference herein, proposes application of the adaptive halting algorithm using the variance of the soft output sequence as the halting criterion. Although the Robertson technique does not require an extra large memory capacity or a large multiplier such as required when using the foregoing cross entropy computation methods, the technique of Robertson nonetheless requires additional multiplier hardware to calculate the variance. The requirement for a multiplier is disadvantageous for low power and low-cost silicon implementations since the additional hardware will increase both the size and power requirements necessary to implement the adaptive halting algorithm.
In view of the foregoing, a need exists in the communication art for an adaptive halting structure and method that does not require use of the passively embedded CRC code and that does not require surplusage multipliers or memory capacity.
The present invention is directed to a structure and method of implementing a direct comparison adaptive halting algorithm and decoder associated with iterative turbo decoding without resorting to use of a passively included CRC code. The soft output sequence observed at each iteration step contains information on three L-valued sequences; the channel information, the a priori information and the extrinsic information. The channel information sequence is constant during the iteration and thus does not have any information on the state of the convergence necessary to halt the iteration process. Thus, the change of the sum of the a priori information and the extrinsic information sequences is observed during each iteration step. The soft output sequence containing the channel information sequence is, however, referred to in order to estimate the state of the convergence, such as disclosed by Hagenauer et al. above. The sum of the a priori information sequence and the extrinsic information sequence contains accurate information on the state of the convergence and thus is quantized into a binary sequence. During an iteration, any changes of the binary sequence are detected. The iteration process is halted once this change can no longer be detected. The foregoing detection at each iteration step can be easily implemented by storing the reference sequence generated by a MAP decoder in each stage of a turbo decoder and updating the stored reference sequence for each stage following each iteration step, which does not seriously increase the hardware size of the decoder.
The present iterative turbo decoding process utilizing the direct comparison algorithm is implemented by dividing each iteration step into two stages. MAP-decoding is performed at each stage of the iteration step. The MAP-decoding produces information sequences at each stage that are then subsequently summed and quantized into binary sequences (reference sequences). The reference sequence at the second stage of one iteration step is stored in a memory location and then de-interleaved. The newly generated reference sequence at the first stage of the next iteration step is directly compared with the foregoing de-interleaved reference sequence and then interleaved. At the second stage of the iteration step, in the same way, the reference sequence generated at the second stage by the MAP decoder is directly compared with the foregoing interleaved reference sequence generated by the first stage MAP decoder. The iteration process is then halted only if the reference sequences at the first and the second stages of the iteration step correspond identically with those same reference sequences generated at the preceding iteration step. Thus, the direct comparison halting algorithmic turbo decoder estimates the state of the convergence in only one iteration step and thus can quickly determine the iteration step to be halted. The direct comparison halting algorithmic turbo decoder can halt the iteration earlier than CRC-based adaptive halting turbo decoders or such decoders otherwise requiring use of passively embedded CRC codes so that the computational complexity of the turbo decoder can be further reduced.
As used herein, the following words have the following meanings. The words xe2x80x9calgorithmic softwarexe2x80x9d mean an algorithmic program used to direct the processing of data by a computer or data processing device. The words xe2x80x9cdata processing devicexe2x80x9d as used herein refer to a CPU, DSP, microprocessor, micro-controller, or other like device and an interface system. The interface system provides access to the data processing device such that data could be entered and processed by the data processing device. The words xe2x80x9cdiscrete dataxe2x80x9d as used herein are interchangeable with xe2x80x9cdigitized dataxe2x80x9d and xe2x80x9cdigitized dataxe2x80x9d as used herein means data which are stored in the form of singularly isolated, discontinuous data or digits. The word xe2x80x9cinterleaverxe2x80x9d as used herein means a single input, single output device that takes sequences of symbols in a fixed alphabet and produces an output sequence of the identical symbols over the same alphabet in a different temporal order. Then for an input sequence xi,ixcex5Z to an interleaver, the output sequence y1,ixcex5Z can be written as y1=xxcfx80(i), where xcfx80 is defined as an invertible function: xcfx80:Zxe2x86x92Z.
In one aspect of the invention, a method and associated structure are implemented to provide a direct comparison adaptive halting algorithm associated with iterative turbo decoding to more efficiently estimate the state of the convergence for a variable rate data communication signal.
In still another aspect of the invention, a method and associated structure are implemented to provide a direct comparison adaptive halting algorithm associated with iterative turbo decoding to estimate the state of the convergence of received communication signals devoid of passively embedded error detection, e.g. CRC, codes.
In yet another aspect of the invention, a method and associated structure are provided to implement a direct comparison adaptive halting algorithm associated with iterative turbo decoding to estimate the state of the convergence of a data communication signal without the necessity of direct reference to soft output sequences.
In another aspect of the invention, a method and associated structure are provided to implement a direct comparison adaptive halting algorithm associated with iterative turbo decoding to estimate the state of the convergence of a data communication signal without requiring either a large memory capacity or a multiplier with a long word length.
Another aspect of the invention is associated with a direct comparison adaptive halting algorithm iterative turbo decoding procedure and structure in which the computational complexity of the decoder(s) can be reduced by about 50% over known iterative turbo decoder structures without degradation in the BER and FER, to estimate the state of the convergence of a data communication signal.
Still another aspect of the invention is associated with a direct comparison adaptive halting algorithm for turbo decoding in which the computational complexity of the adaptive halting algorithm associated with a turbo decoder is substantially reduced in comparison with those CRC-based adaptive halting algorithms for turbo decoders known in the art.